public class test3 {
}
// https://leetcode.cn/problems/reorder-list/
//class Solution {
//    public void reorderList(ListNode head) {
//        if(head.next==null || head.next.next==null) return;
//        // 1. 快慢指针找到中间节点
//        ListNode fast=head;
//        ListNode slow=head;
//        ListNode prev=new ListNode(-1);// slow的前一个节点
//        prev.next=slow;
//        while(fast!=null && fast.next!=null) {  // 要先判断fast,否则会空指针异常
//            fast=fast.next.next;
//            slow=slow.next;
//            prev=prev.next;
//        }
//        prev.next=null;// 终止前半段
//        // 此时slow的位置就是后半段的起点
//        // 2. 逆置后半段,应该在原链表的原节点上进行改动,不能创建新节点!!!
//        ListNode newHead=reverseList(slow);
//        // 3. 合并两链表
//        mergeList(head,newHead);
//    }
//    public static ListNode reverseList(ListNode slow) {
//        ListNode prev=null;
//        ListNode cur=slow;
//        while(cur!=null) {
//            ListNode curN=cur.next;
//            cur.next=prev;
//            prev=cur;
//            cur=curN;
//        }
//        return prev;
//    }
//
//    public static void mergeList(ListNode head1,ListNode head2) {
//        ListNode cur1=head1;
//        ListNode cur2=head2;
//        ListNode cur1N=cur1.next;
//        ListNode cur2N=cur2.next;
//        while(cur1N!=null) {
//            cur1.next=cur2;
//            cur2.next=cur1N;
//            cur1=cur1N;
//            cur2=cur2N;
//            if(cur1N!=null)cur1N=cur1N.next;
//            if(cur2N!=null)cur2N=cur2N.next;
//        }
//        cur1.next=cur2;
//    }
//}
